﻿/* Write a program that finds the sequence of maximal sum in given array. Example:
	{2, 3, -6, -1, 2, -1, 6, 4, -8, 8}  {2, -1, 6, 4}
	Can you do it with only one loop (with single scan through the elements of the array)?
*/

using System;

class FindMaxSequenceSum
{
    static void Main()
    {
        uint N;
        bool iProvided = false;
        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
            else iProvided = true;
            Console.Write("Enter N: ");
        } while (UInt32.TryParse(Console.ReadLine(), out N) == false|| N < 1);

        iProvided = false; //reset iProvided
        int[] nums = new int[N];
        for (int i = 0; i < nums.Length; i++)
        {
            iProvided = false;
            do
            {

                if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
                else iProvided = true;
                Console.Write("Enter element {0}: ", i + 1);
            } while (Int32.TryParse(Console.ReadLine(), out nums[i]) == false);
        }
        for (int i = 0; i < nums.Length; i++) Console.WriteLine(nums[i]);
        
        //solving using the Maximum Subarray Problem algorithm
        int MSF = nums[0], MEH = nums[0]; //declare max so far, max ending with starting element the first element
        int begin = 0, begin_temp = 0, end = 0;
        //Find sequence by looping through
        //FOR CONTIGUOUS (SEQUENTIAL) ELEMENTS
        for (int i = 1, a = 1; i < nums.Length; i++)
        {
            //calculate MEH
            MEH += nums[i];
            if (nums[i] > MEH)
            {
                MEH = nums[i];
                begin_temp = i;
            }
            //calculate MSF
            if (MEH > MSF)
            {
                MSF = MEH;
                begin = begin_temp;
                end = i;
            }
        }
        string nStr = null;
        Console.WriteLine("------------------------------");
        Console.WriteLine("Sum (max. seqental): {0}\r\nElements:", MSF);
        for (int i = begin; i <= end; i++) nStr += nums[i] + ", ";
        nStr = nStr.Substring(0, nStr.Length-2);
        Console.WriteLine("{0}\r\n", nStr);

    }
}
